// 560.和为k的子数组

package LeetcodeHot100;

import java.util.HashMap;
import java.util.Map;

public class Solution560 {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        // dp[i] 表示 0 ~i 的和，也就是前缀和
        Map<Integer, Integer> map = new HashMap<>(); // (前缀和，个数) 会出现 1100 前缀和为2的数量有3个的情况
        map.put(0, 1); // 空串和为0，数量为1
        int pre = 0; // 用于记录前缀和
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - k)) { // 判断前面是否有前缀和 a，与 k 相加等于 pre ，即 pre-a=k
                count += map.get(pre - k); // 如果有则表示 a~pre 是和为 k 的子串
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1); // 将当前的前缀和加入哈希表中
        }
        return count;
    }
}
